package com.wang.leetcode;

/**
 * @Author: along
 * @Create: 2021/5/7
 * @Description:最大子序和（给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。）
 */
public class Solution53 {
    //枚举所有情况
    public static int maxSubArray1(int[] nums) {
        int sum = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] + sum >= sum) {//说明nums[i] >= 0 累加后使最大子序和增大
                if (sum < 0) { //当前的sum 如果小于0  舍弃sum 从nums[i]再开始  小于0拖后腿
                    sum = nums[i];
                } else {
                    sum += nums[i];//sum > 0 累加继续往下
                }
            } else {//nums[i] < 0
                if (nums[i] + sum >= 0) {//nums[i] < 0 但是sum累加nums[i]后大于0 可以先保留
                    sum += nums[i];
                } else {//nums[i] 已经小于0了，并且sum累加nums[i]也小于0  越加越小 所以舍弃之前的sum
                    sum = nums[i];
                }
            }
            if (sum > max) {//把sum和之前得到的max比较
                max = sum;
            }
        }
        return max;
    }
    //官方动态规划解
    public static int maxSubArray2(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;

    }
        //for test
        public static void main (String[]args){
            int[] nums = new int[]{5, 10, -4, 8, 6, -1, 7, -6, -10, 20};
            System.out.println(maxSubArray1(nums));
            System.out.println(maxSubArray2(nums));
        }
    }
